package com.algorithm.array;

import java.util.LinkedList;
import java.util.List;

/**
 * Created by dongxie on 2021/12/9.
 * https://leetcode-cn.com/problems/spiral-matrix/
 * 顺时针螺旋顺序
 */
public class SpiralMatrixOrder {
    public static void main(String[] args) {

    }

    /**
     * 这里的方法不需要记录已经走过的路径，所以执行用时和内存消耗都相对较小
     * 1.首先设定上下左右边界
     * 2.其次向右移动到最右，此时第一行因为已经使用过了，可以将其从图中删去，体现在代码中就是重新定义上边界
     * 3.判断若重新定义后，上下边界交错，表明螺旋矩阵遍历结束，跳出循环，返回答案
     * 4.若上下边界不交错，则遍历还未结束，接着向下向左向上移动，操作过程与第一，二步同理
     * 5.不断循环以上步骤，直到某两条边界交错，跳出循环，返回答案
     *
     * @return
     */
    public List<Integer> spiralMatrixOrder(int[][] matrix) {
        List<Integer> res = new LinkedList<>();
        if (matrix.length == 0) {
            return res;
        }
        int up = 0, down = matrix.length - 1, left = 0, right = matrix[0].length - 1;
        while (true) {
            //向右
            for (int col = left; col <= right; ++col) {
                res.add(matrix[up][col]);
            }
            //修正，若上边界++大于下边界，break
            if (++up > down) {
                break;
            }
            //向下
            for (int row = up; row <= down; ++row) {
                res.add(matrix[row][right]);
            }
            //修正，若右边界--小于左边界，break
            if (--right < left) {
                break;
            }
            //向左
            for (int col = right; col >= left; --col) {
                res.add(matrix[down][col]);
            }
            //修正，若下边界--大于上边界，break
            if (--down < up) {
                break;
            }
            //向上
            for (int row = down; row >= up; --row) {
                res.add(matrix[row][left]);
            }
            //修正，若左边界++大于右边界，break
            if (++left > right) {
                break;
            }
        }
        return res;
    }
}
